package org.fly.alg;

import java.util.ArrayList;
import java.util.List;

public class DNTrie {
    private String data;
    private boolean flag;
    private List<DNTrie> children;
    
    public DNTrie() {
        this("", false);
    }
    
    public DNTrie(String data, boolean flag) {
        this.data = data;
        this.flag = flag;
    }
    
    public boolean insert(String dn) {
        String[] dns = dn.split("\\.");
        return insert(dns, dns.length);
    }

    private boolean insert(String[] dns, int index) {
        --index;
        if (null == children) {
            add(dns, index);
            return true;
        }
        for (DNTrie child : children) {
            if (dns[index].equals(child.data)) {
                if (child.flag) {
                    return false;
                }
                if (index == 0) {
                    add(dns, index);
                    return true;
                }
                return child.insert(dns, index);
            }
        }
        add(dns, index);
        return true;
    }

    private void add(String[] dns, int index) {
        if (-1 == index) {
            return;
        }
        if (children == null) {
            children = new ArrayList<DNTrie>();
        }
        DNTrie trie = new DNTrie(dns[index],  0 == index);
        trie.add(dns, --index);
        children.add(trie);
    }

    private boolean contains(String[] dns, int index) {
        --index;
        if (null == children) {
            return false;
        }
        for (DNTrie child : children) {
            if (dns[index].equals(child.data)) {
                if (child.flag) {
                    return true;
                }
                if(index == 0) {
                    return false;
                }
                return child.contains(dns, index);
            }
        }
        return false;
    }

    public boolean contains(String dn) {
        String[] dns = dn.split("\\.");
        return contains(dns, dns.length);
    }
}
